#include <bst.h>

bst_link_t bst_search_link(bst_t* bst_p, const void* data_p,
			   bst_link_t** write_link_pp,
			   const bst_link_t* endn_p) {
	bst_node_t** link_pnp = &(bst_p->root_pn);
	bst_node_t* node_pn;
	bst_link_t* write_link_p = *write_link_pp;
	while (1) {
		node_pn = *link_pnp;
		write_link_p->node_link_pnp = link_pnp;
		write_link_p->node_pn = node_pn;
		write_link_p++;
		if (unlikely(node_pn == nullptr || write_link_p >= endn_p)) {
			break;
		}

		bst_node_t* node_p = node_pn;
		const void* node_data_p = bst_get_data_p(bst_p, node_p);
		iword_s cmp_result = bst_p->cmp_f(data_p, node_data_p);
		if (unlikely(cmp_result == 0)) {
			break;
		} else if (cmp_result < 0) {
			link_pnp = &(node_p->left_pn);
		} else {
			link_pnp = &(node_p->right_pn);
		}
	}
	*write_link_pp = write_link_p;
	bst_link_t result = {
		.node_link_pnp = link_pnp,
		.node_pn = node_pn,
	};
	return result;
}
